Content addressable memories (CAMs) can provide rapid matching between a specific pattern of received data bits, commonly known as a search key or comparand, and data values stored in an associative CAM memory array. CAMs can provide advantageous matching speeds as entries (or locations) of an entire CAM array can be searched in parallel. In a CAM, if a match occurs for every bit in a location with every corresponding bit in the comparand, a match flag can be asserted to let a user know that data in the comparand was found in memory. In addition, a value corresponding to the match can be returned. Thus, the result is determined from finding a matching value (content), and not from providing the address of the value as done for a random access memory (RAM.).
One particularly useful type of CAM is a ternary (or tertiary) CAM (or TCAM). A TCAM can include two types of entries: mask and data. A mask entry can indicate which bits in a corresponding data entry take part in a compare/search operation. For example, a mask bit=1 can indicate that the bit in the corresponding data entry can be compared against the corresponding bit in the compare data. In contrast, a mask bit=0 can indicate that the corresponding data entry bit is not compared and is always assumed to evaluate to be matched. Thus, a masked bit will not generate a mismatch indication even if the masked data value bit is different than the corresponding comparand value bit. The logical operation for a ternary CAM, on a bit-by-bit basis, can be represented by the logic:Match[x]=(Compare[x]==Data[x])|˜Mask[x]. The preceding description is that of a “full” TCAM device or system. Such a system typically includes a full TCAM array in which each separate memory location includes a mask and a data field.
A block diagram of a conventional full TCAM is shown in FIG. 10, and designated by the general reference character 1000. In a full Ternary CAM, one mask can control a match (i.e., search) operation on one associated data value. Thus, the full TCAM 1000 includes data entries 1002 with corresponding mask entries 1004. That is, mask entry “Mask=A” can mask match operations for data entry “Data=0”, mask entry “Mask=B” can mask match operations for data entry “Data=1”, etc. It is understood that each such data/mask entry pair can be accessed at a unique address according to control logic. One such arrangement is shown in FIG. 11.
FIG. 11 is a block diagram showing a conventional write-to-mask operation of a conventional full TCAM. FIG. 11 shows two mask locations 1104-0 and 1104-1 (corresponding data locations being excluded to avoid cluttering the view) as well as the corresponding control logic 1106 for such locations. Control logic 1106 can include row decoders 1106-0 and 1106-1. As shown in the figure, each row decoder (1106-0 and 1106-1) can operate according to a unique row address.
In a conventional write-to-mask operation, a unique row address (ADR) 1108 can be provided to row decoders (1106-0 and 1106-1). In addition, mask write data 1110 can be applied via bit lines 1112 corresponding to the mask locations (1104-0 and 1104-1). When the unique address 1108 corresponds to that of a row decoder (1106-0 and 1106-1), the corresponding row decoder can activate a mask word line, resulting in the write data on bit lines 1112 being written into the corresponding mask location.
Although more flexible, because each memory location includes both mask and data fields, the size and corresponding cost of a full TCAM system can be relatively high, particularly for larger memory capacities.
To reduce the size of a TCAM system or device, it is often desirable to map-mask-to-data entries in the form of a 1:N mapping. That is, in a full TCAM arrangement, mask-to-data mapping is of the form 1:1. To reduce overall size of a TCAM, mask-to-data mapping can be 1:N, where N>1. Such an arrangement is considered a “pseudo” TCAM.
One example of a pseudo TCAM is shown in FIG. 12, and designated by the general reference character 1200. Pseudo TCAM 1200 can include data entries 1202 with corresponding mask entry 1204. In the arrangement shown, a single mask entry 1204 (mask entry “Mask=A”) can mask match operations for eight different data entries “Data=0” to “Data=7”.
Among the numerous applications for memory systems using TCAM devices or TCAM systems are network search engines (NSEs). An NSE can use TCAMs to provide fast searches of a database, list, or pattern. A block diagram of a line card that includes an NSE having a conventional pseudo TCAM system is shown in FIG. 13 and designated by the general reference character 1300. Line card 1300 can include a network processing unit (NPU) and/or application specific integrated circuit (ASIC) 1302 and NSE 1304. Generally, a conventional NSE 1304 can include a control circuit 1306 or control logic for controlling operation of a pseudo TCAM system 1308.
Similarly, FIG. 14 illustrates another line card 1400 having an NSE 1404 with a conventional full TCAM system 1408.
Due to the differences in the number of mask entries versus corresponding data entries between a full TCAM and the pseudo TCAM, conventional approaches require that two completely different TCAM devices be designed and implemented. The disadvantages of such an approach can include longer product development time and increased cost due to the resource needs for each a unique instantiation of a full TCAM and a pseudo TCAM. As one very particular example, each pseudo TCAM having a mapping of 1:N for mask-to-data correspondence can require a new design and development for each different value of N.
Another disadvantage to the above conventional approaches can be verification. Each unique instantiation (full TCAM or each different “N” mapping of a pseudo TCAM) can require a verification test bench and test suite written to completely validate the design. This can increase product development time, resource requirements, and cost.
Accordingly, it would be desirable to arrive at some TCAM circuit and/or method that can address the above drawbacks of the conventional approaches noted above.